Vĩnh là cháu trực hệ 8 đời của Lương Hiếu vương Lưu Vũ. Phả hệ các đời Lương vương từ Lưu Vũ đến Lưu Vĩnh như sau: Lưu Vũ → Lưu Mãi → Lưu Tương → Lưu Vô Thương → Lưu Định Quốc → Lưu Toại → Lưu Gia → Lưu Lập → Lưu Vĩnh. Cha là Lưu Lập, được nối tước Lương vương. Bởi Lập đi lại với ngoại thích họ Vệ thời Hán Bình đế, bị Vương Mãng làm tội, nên ông không được kế thừa vương tước.